#ifndef _MATRIXGRAPH_H_
#define _MATRIXGRAPH_H_

#include <iostream>
#include"Graph.h"

template <typename T>
class MatrixGraph:public Graph{

protected:
	int**	matrix;
	T* vertex_infos;

public:
	MatrixGraph(int vertex_num, T* vertex_infos);
	MatrixGraph(const MatrixGraph& g);
	MatrixGraph& operator=(const MatrixGraph& g);
	virtual ~MatrixGraph();

	Edge GetFirstEdge(int vertex);
	Edge GetNextEdge(Edge pre_edge);
	bool SetEdge(int from, int to, int weight =1);
	bool DelEdge(int from, int to);
	bool IsEdge(Edge edge);

	void Visit(int vertex);
	void DumpGraph(std::ostream& os);
	void DumpVertexInfo(std::ostream& os, int index);
};

template<typename T>
MatrixGraph<T>::MatrixGraph(int vertex_num, T* vertex_infos):Graph(vertex_num){
	this->vertex_infos = new T[vertex_num];
	for(int i=0;i<this->vertex_num;i++){
		this->vertex_infos[i] = vertex_infos[i];
	}
	this->matrix = (int * *)(new int*[this->vertex_num]);
	for(int i=0;i<this->vertex_num; i++){
		this->matrix[i] = new int [this->vertex_num];
		for(int j=0;j<this->vertex_num;j++){
			this->matrix[i][j] = 0;
		}
	}
}

template<typename T>
MatrixGraph<T>::MatrixGraph(const MatrixGraph& g):Graph(g){
	if(this!=&g){
		this->vertex_infos = new T[vertex_num];
		for(int i=0;i<this->vertex_num;i++){
			this->vertex_infos[i] = g.vertex_infos[i];
		}
		this->matrix = (int * *)(new int*[this->vertex_num]);
		for(int i=0;i<this->vertex_num; i++){
			this->matrix[i] = new int [this->vertex_num];
			for(int j=0;j<this->vertex_num;j++){
				this->matrix[i][j] = g.matrix[i][j];
			}
		}
	}
}

template<typename T>
MatrixGraph<T>& MatrixGraph<T>::operator=(const MatrixGraph& g){
	if(this!=&g){
		Graph::operator=(g);
		this->vertex_infos = new T[vertex_num];
		for(int i=0;i<this->vertex_num;i++){
			this->vertex_infos[i] = g.vertex_infos[i];
		}
		this->matrix = (int * *)(new int*[this->vertex_num]);
		for(int i=0;i<this->vertex_num; i++){
			this->matrix[i] = new int [this->vertex_num];
			for(int j=0;j<this->vertex_num;j++){
				this->matrix[i][j] = g.matrix[i][j];
			}
		}
	}
	return *this;
}
template<typename T>
MatrixGraph<T>::~MatrixGraph(){
	delete[] this->vertex_infos;
	for(int i=0;i<this->vertex_num;i++){
		delete[] this->matrix[i];
	}
	delete[] this->matrix;
}
template<typename T>
Edge MatrixGraph<T>::GetFirstEdge(int vertex){
	Edge e(vertex,-1,0);
	int* vs = this->matrix[vertex];
	for(int i=0;i<this->vertex_num;i++){
		if(this->matrix[vertex][i]!=0){
			e.weight = this->matrix[vertex][i];
			e.to = i;
			break;
		}
	}
	return e;
}

template<typename T>
Edge MatrixGraph<T>::GetNextEdge(Edge pre_edge){
	Edge e(pre_edge.from,-1,0);
	int *vs = this->matrix[pre_edge.from];
	for(int i = pre_edge.to+1; i <this->vertex_num; i++){
		if(this->matrix[pre_edge.from][i]!=0){
			e.to = i;
			e.weight = this->matrix[pre_edge.from][i];
			break;
		}
	}
	return e;
}

template<typename T>
bool MatrixGraph<T>::SetEdge(int from, int to, int weight){
	if((from<this->vertex_num)&&(to<this->vertex_num)&&(from>=0)&&(to>=0)&&(from!=to)){
		this->matrix[from][to] = weight;
		this->IncEdge(from,to);
		return true;
	}
	return false;
}

template<typename T>
bool MatrixGraph<T>::DelEdge(int from, int to){
	if((from<this->vertex_num)&&(to<this->vertex_num)&&(from>=0)&&(to>=0)&&(from!=to)){
		if(this->matrix[from][to]!=0){
			this->matrix[from][to] = 0;
			this->DecEdge(from,to);
			return true;
		}
	}
	return false;
}

template<typename T>
bool MatrixGraph<T>::IsEdge(Edge edge){
	if((edge.from<this->vertex_num)&&(edge.to<this->vertex_num)&&(edge.from>=0)&&(edge.to>=0)&&(edge.from!=edge.to)){
		if(this->matrix[edge.from][edge.to]!=0){
			return true;
		}
	}
	return false;
}

template<typename T>
void MatrixGraph<T>::Visit(int vertex){
	std::cout<<"["<<this->vertex_infos[vertex]<<"]";
}

template<typename T>
void MatrixGraph<T>::DumpGraph(std::ostream& os){
	for(int from=0;from<this->vertex_num;from++){
		os<<this->vertex_infos[from]<<":";
		for(int to=0;to<this->vertex_num;to++){
			os<<"["<<this->matrix[from][to]<<"]";
		}
		os<<"\n";
	}
	os<<"\n";
}

template<typename T>
void MatrixGraph<T>::DumpVertexInfo(std::ostream& os, int index){
	os<<this->vertex_infos[index];
}


#endif // _MATRIXGRAPH_H_
